package cm.unit3.theme4;

import cm.commom.ListNode;

public class MergeTwoSortedList {

    public static ListNode insertNode(ListNode begin,ListNode node){
        ListNode cursor = begin;
        ListNode ptr = begin;
        while (cursor!=null){
            if (cursor.val > node.val){
                break;
            }
            ptr = cursor;
            cursor = cursor.next;
        }
        node.next = cursor;
        ptr.next = node;
        return node;
    }

    public ListNode Merge(ListNode list1, ListNode list2){
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }
        ListNode head;
        ListNode ptr;
        // 一个
        if (list1.val < list2.val){
            head = list1;
            for (ListNode node=list2;node!=null;node=ptr){
                ptr = node.next;
                list1 = insertNode(list1,node);
            }
        }else{
            head = list2;
            for (ListNode node=list1;node!=null;node=ptr){
                ptr = node.next;
                list2 = insertNode(list2,node);
            }
        }
        return head;
    }

    public ListNode Merge02(ListNode list1,ListNode list2) {
        ListNode sPtr;
        ListNode bPtr;
        ListNode head;

        if(list1==null)
            return list2;
        if(list2==null)
            return list1;

        if(list1.val < list2.val){
            head = list1;
            sPtr = list1;
            bPtr = list2;
        }
        else{
            head = list2;
            sPtr = list2;
            bPtr = list1;
        }
        ListNode bTmp;
        // 把首元素大的链表合并号首元素小的链表
        while(bPtr!=null && sPtr!=null)
        {    // 查找
            while(sPtr.next!=null && sPtr.next.val < bPtr.val)
                sPtr = sPtr.next;
            // 记录b的下一个结点
            bTmp = bPtr.next;
            // 改链
            bPtr.next = sPtr.next;
            sPtr.next = bPtr;
            sPtr = bPtr;
            bPtr = bTmp;
        }
        return head;
    }
}
